package homework;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class tree {


class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}
int getHigh(TreeNode root){
    if(root==null)return 0;
    int leftHigh=getHigh(root.left);
    int rightHigh=getHigh(root.right);
    return 1+Math.max(leftHigh,rightHigh);
}
TreeNode getNode(TreeNode root, int val){
    //这颗树为空，返回null
    if(root==null)return null;
    //找到了返回
    if(root.val==val)return root;

        //找不到，向下访问
    TreeNode node=null;
        if (root.left != null) node= getNode(root.left, val);
        //如果在左子树找到了，返回结果
        if(node!=null)return node;
 //如果在左子树没有找到返回右子树的结果
        return getNode(root.right, val);
    }
//统计二叉树的节点个数
    int getNums(TreeNode root){
    if(root==null)return 0;
    return 1+getNums(root.left)+getNums(root.right);
    }

    //先、中、后序遍历该二叉树（采用递归算法）

    //中序遍历
 void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
     System.out.println(root.val);
        inorder(root.right);
    }
    //前序遍历
    void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }
    //后序遍历
    void  postorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }

    //（5）层序遍历该二叉树；
void show(TreeNode node){
    if(node==null)return;
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(node);
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i=1;i<=size;i++){
            TreeNode p= queue.poll();
            System.out.print(p.val+" ");
            queue.offer(p.left);
            queue.offer(p.right);
        }
        System.out.println();//换行
    }
}


    //（6）判断值为x和y的结点是否互为兄弟结点，假设这样的结点值是唯一的

    boolean isBrother(TreeNode node,int val1,int val2){
    //找不到了
    if(node==null)return false;
    //如果当前节点的儿子是兄弟节点
        if(node.left!=null&&node.right!=null&&((node.left.val==val1&&node.right.val==val2)||(node.right.val==val1&&node.left.val==val2)))return true;
        boolean temp=false;
        if(node.left!=null){
        temp=isBrother(node.left,val1,val2);
        if(temp)return true;//如果在左子树找到了，返回
        }
        //在右子树上找
        return isBrother(node.right,val1,val2);
    }

    //统计节点数,然后通过队列层序遍历,遇到左儿子或者右儿子为null的话,先把非空停下来,比较节点数和队列层序遍历得到的数目是否一致
    //层序遍历，空，后面右不空，返回false
    boolean isComplete2(TreeNode node){
    if(node==null)return false;
    int sum=getNums(node);
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(node);
        int num=1;
        while(!q.isEmpty()){
            TreeNode p= q.poll();

          int temp=1;
         if(p.left!=null){q.offer(p.left);num++;}else temp=0;
         if(p.right!=null){q.offer(p.right);num++;}else temp=0;
         if(temp==0)break;
        }
        return sum==num;
    }

    boolean isComplete(TreeNode node){
        if(node==null)return false;
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(node);
        boolean flag=false;//标记
        while(!q.isEmpty()){
            TreeNode p= q.poll();
            if(p==null)flag=true;//找到了空节点
            if(p!=null){
                if(flag)return false;
                q.offer(p.left);
                q.offer(p.right);
            }
        }
return true;
    }

}
